""" A graph is a very flexible data structure that consists of a set of nodes
and edges. This data structure can be used to support many machine learning
algorithms - Neural Networks, Bayesian Networks, Influence Diagrmas, Kalmann
Filters, etc. """

from utils import dict2xml

#______________________________________________________________________________
class BaseObject(object):
    def __init__(self, **kwds):
        self.__dict__.update(kwds)
        self.type = self.__class__.__name__.lower()
    
    def __getattr__(self, attr):
        getattr(self.__dict__, attr, None)

#______________________________________________________________________________
class Node(BaseObject):
    """ The base class for all graph nodes. The only requirement is a name. """
    def __init__(self, **kwds):
        BaseObject.__init__(self, kwds)
        if name not in kwds:
            raise Exception, "Please specify a name for this node."
        
    def __eq__(self, other):
        return self.name == other.name

#______________________________________________________________________________
class Edge(BaseObject):
    """ The base class for all graph edges. """
    def __init__(self, node1, node2, **kwds):
        BaseObject.__init__(self, kwds)
        self.nodes = [node1, node2]

    def __eq__(self, other):
        nameset1 = set([n.name for n in self.nodes]) 
        nameset2 = set([n.name for n in other.nodes])
        return nameset1 == nameset2

#______________________________________________________________________________
class Graph(BaseObject):
    """ A collection of nodes and edges.  
            * The 2 nodes for each edge are automatically added to the graph 
            * It is OK to have more than one edge for the same pair of nodes
            * A node is not required to belong to an edge
            * An edge can connect a node with itself
            * All node names must be unique """
    def __init__(self, nodes=[], edges=[], **kwds):
        BaseObject.__init__(self, kwds)
        self.nodes, self.edges = set(), set()
        nodeMap = {}
        if nodes:    # Store the nodes; create if necessary
            for n in nodes:
                if   isinstance(n, str):  node = Node(name=n)
                elif isinstance(n, Node): node = n
            self.nodes.add(node)
            nodeMap[node.name] = node
        if edges:    # Store the edges; create if necessary
            for e in edges:
                # Check if it's an edge object
                if isinstance(e, Edge):
                    [node1, node2] = e.nodes
                    self.nodes.add(node1)
                    self.nodes.add(node2)
                    continue   
                # It's not an edge object but a pair of nodes                 
                (n1, n2) = e
                if isinstance(n1, str) and isinstance(n2, str):
                    node1 = nodeMap[n1]
                    node2 = nodeMap[n2]
                elif isinstance(n1, Node) and isinstance(n2, Node):
                    node1, node2 = n1, n2
                edge = Edge(node1, node2)
                self.edges.append(edge)
    
    def getNode(self, name):
        for node in self.nodes:
            if node.name == name:
                return node
        return None
        
    def getNeighbors(self, node):
        """ Returns all nodes directly connected to this one. """
        neighbors = set()
        for (name1, name2) in self.edges.iteritems():
            if name1 == node.name:
                neighbors.add(name2)
            if name2 == node.name:
                neighbors.add(name1)
        return neighbors

#______________________________________________________________________________
class DirectedEdge(Edge):
    """ An edge with directionality.  One node is called the parent, while
        the other is called the child. """
    def __init__(self, parent=None, child=None, **kwds):
        BaseObject.__init__(self, kwds)
        self.parent, self.child = parent, child

    def __eq__(self, other):
        if not isinstance(other, DirectedEdge):
            return False
        return (self.parent.name == other.parent.name) and \
               (self.child.name == other.child.name)

#______________________________________________________________________________
class Digraph(Graph):
    """ A directed graph is a graph where all edges are directed edges """
    def __init__(self, nodes=[], edges=[], **kwds):
        BaseObject.__init__(self, kwds)
        self.nodes, self.edges = set(), set()
        nodeMap = {}
        if nodes:    # Store the nodes; create if necessary
            for n in nodes:
                if   isinstance(n, str):  node = Node(name=n)
                elif isinstance(n, Node): node = n
            self.nodes.add(node)
            nodeMap[node.name] = node
        if edges:    # Store the edges; create if necessary
            for e in edges:
                # Check if it's an edge object
                if isinstance(e, Edge):
                    [node1, node2] = e.nodes
                    self.nodes.add(node1)
                    self.nodes.add(node2)
                    continue   
                # It's not an edge object but a pair of nodes                 
                (n1, n2) = e
                if isinstance(n1, str) and isinstance(n2, str):
                    node1 = nodeMap[n1]
                    node2 = nodeMap[n2]
                elif isinstance(n1, Node) and isinstance(n2, Node):
                    node1, node2 = n1, n2
                edge = Edge(node1, node2)
                self.edges.append(edge)
        
    def getParents(self, node):
        pass
    
    def getChildren(self, node):
        pass

#______________________________________________________________________________
class DAG(Digraph):
    """ A Directed Acyclic Graph (DAG) is a directed graph where no directed
        cycles - that is, there is no directed path that starts and ends at the 
        same node. """
    def __init__(self, **kwds):
        BaseObject.__init__(self, kwds)
        pass

#______________________________________________________________________________
class Tree(Digraph):
    """ A tree is a directed graph with the following constraints:
           * There must be exactly one node with no parent
           * All other nodes have a single, unique parent """
    def __init__(self, root=None, **kwds):
        BaseObject.__init__(self, kwds)
        pass
        
    def getParent(self, node):
        pass
    
    def getChildren(self, node):
        pass